/*
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
*/

/**
 * @param {string} s
 * @return {string}
 */
 var longestPalindrome = function(s) {
    
    let res = ''
    let dp = new Array(s.length).fill(0).map(v => new Array(s.length).fill(0))

    for(let i = s.length - 1; i >= 0; i--){
        for(let j = i; j < s.length; j++){
            // dp[i][j] = dp[i - 1][j + 1] && s[i] === s[j]
            dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])
            res = res.length < (j - i + 1) && dp[i][j] ? s.substring(i, j + 1) : res
        }
    }
    return res
};